package com.lw.leetcode.binary.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2080. 区间内查询数字的频率
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/27 20:40
 */
public class RangeFreqQuery {

    private Map<Integer, List<Integer>> map = new HashMap<>();
    public RangeFreqQuery(int[] arr) {
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            map.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
        }
    }


    public int query(int left, int right, int value) {
        List<Integer> list = map.get(value);
        if (list == null) {
            return 0;
        }
        return binary3(list, right) - binary2(list, left) - 1;
    }

    public int binary2(List<Integer> nums, int target) {
        if (nums.get(0) >= target) {
            return -1;
        }
        int st = 0;
        int end = nums.size() - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums.get(m) < target) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

    private int binary3(List<Integer> nums, int target) {
        int end = nums.size() - 1;
        if (nums.get(end) <= target) {
            return end + 1;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (nums.get(m) > target) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }


}
